◀ Prev · Parts · Full · Next ▶

As discussed above, every node needs to find its minimum weight outgoing incident edge after the receipt of a broadcast message from the core. If node n {\displaystyle n} receives a broadcast, it will pick its minimum weight basic edge and send a message to the node n ′ {\displaystyle n'} on the other side with its fragment's ID and level. Then, node n ′ {\displaystyle n'} will decide whether the edge is an outgoing edge and send back a message to notify node n {\displaystyle n} of the result. The decision is made according to the following:

1. F r a g m e n t I D ( n ) = F r a g m e n t I D ( n ′ ) {\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)={\mathit {Fragment}}_{\mathit {ID}}(n')} . That is, nodes n {\displaystyle n} and n ′ {\displaystyle n'} belong to same fragment, so the edge is not outgoing.

2. F r a g m e n t I D ( n ) ≠ ≠ F r a g m e n t I D ( n ′ ) {\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')} and L e v e l ( n ) ≤ ≤ L e v e l ( n ′ ) {\displaystyle {\mathit {Level}}(n)\leq {\mathit {Level}}(n')} . That is, nodes n {\displaystyle n} and n ′ {\displaystyle n'} belong to the different fragments, so the edge is outgoing.

3. F r a g m e n t I D ( n ) ≠ ≠ F r a g m e n t I D ( n ′ ) {\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')} and L e v e l ( n ) > L e v e l ( n ′ ) {\displaystyle {\mathit {Level}}(n)>{\mathit {Level}}(n')} . We cannot make any conclusion. The reason is that the two nodes may belong to the same fragment already, but node n ′ {\displaystyle n'} has not discovered this fact yet due to the delay of a broadcast message. In this case, the algorithm lets node n ′ {\displaystyle n'} postpone the response until its level becomes higher than or equal to the level it received from node n {\displaystyle n} .

◀ Prev · Parts · Full · Next ▶